from random import choice

class TicTacToe:
	def __init__(self):
		#initial board is a list with 9 empty spaces
		self.board = [None]*9
		#respective players winList, when the list is empty, no more winning moves can be made resulting in a draw
		#if there is an empty winType within the winList, that means that this player has managed
		#to place his marker on all locations within this winType and has won the game
		self.player1WinList = [[0,1,2], [3,4,5], [6,7,8], [0,3,6,], [1,4,7], [2,5,8], [0,4,8], [2,4,6]]
		self.player2WinList = [[0,1,2], [3,4,5], [6,7,8], [0,3,6,], [1,4,7], [2,5,8], [0,4,8], [2,4,6]]
	
	#places playerNr on position in board IF it's a legal move
	#positions are zero based!
	def placeMarker(self, playerNr, position):
		if playerNr not in [1, 2]:# or position not in range(0, 9) or self.board[position] != None :
			raise ValueError("PlayerNr must be either 1 or 2")
		elif position not in range(0, 9):
			raise ValueError("Position must be in range 0, 8")
		elif self.board[position] != None:
			raise ValueError("Illegal move: position already occupied")
		#legal input
		else:
			#mark board with playerNr
			self.board[position] = playerNr
			
			if playerNr == 1:
				self.updateWinList(position, self.player1WinList)
				self.removeFromWinList(position, self.player2WinList)
			
			else:
				self.updateWinList(position, self.player2WinList)
				self.removeFromWinList(position, self.player1WinList)
				
			resultFromMove = self.checkResult()
			
			return resultFromMove
	
	#Goes through all possible winTypes player has and looks for his move. If it's found it's removed from the winType
	def updateWinList(self, position, winList):
		for winType in winList:
			if position in winType:
				winType.remove(position)
	
	#Goes through all remaining winTypes player has. If position is found, the winType is removed from the list as the move cannot result in a win anymore
	def removeFromWinList(self, position, winList):			
		for winType in winList:
			if position in winType:
				winList.remove(winType)
		#this needs to run twice because python skips over a winType if there are two in a row that match the position
		for winType in winList:
			if position in winType:
				winList.remove(winType)
				
	#checks if game is over, returns:
	#Draw = 0
	#Player1 won = 1
	#Player2 won = 2
	#Game is ongoing = None
	def checkResult(self):
		if not self.player1WinList and not self.player2WinList:
			#Both lists empty: No more winTypes = Draw
			return 0
		
		else:
			for winType in self.player1WinList:
				#if there is an empty winType list in winList, player1 won!
				if not winType:
					return 1
					
			for winType in self.player2WinList:
				#if there is an empty winType list in winList, player2 won!
				if not winType:
					return 2
		
		#Continue Game
		return None
	
	def getComputerMove(self):
		myMove = None
		try:
			if self.player1WinList:
				if len(min(self.player1WinList, key = len)) == 1:
					myMove = min(self.player1WinList, key = len)[0]

			if self.player2WinList:
				if len(min(self.player2WinList, key = len)) == 1:
					myMove = min(self.player2WinList, key = len)[0]
				else:
					if not myMove:
						myMove = choice(min(self.player2WinList, key = len))
			else:
				myMove = self.board.index(None)
				
			return myMove
			
		except ValueError:
			print "caught error"

	def getBoard(self):
		return self.board
			
		